Integrating overlay logical networks into cloud provider networks introduces new challenges not found in either system alone. For example, virtual private clouds (VPCs) provided by some cloud providers do not allow for transitive routing using the cloud-provided network making it difficult to route traffic requiring a service provided at a service VPC to the service VPC as part of a route from a source VPC to a destination VPC. Additionally, some services provided by a cloud provider rely on the use of the cloud-provider assigned addresses and don't integrate well with compute nodes assigned addresses in an overlay logical network.